Search for: All records

Filter banks on graphs are shown to be useful for analyzing data defined over networks, as they decompose a graph signal into components with low variation and high variation. Based on recent node-asynchronous implementation of graph filters, this study proposes an asynchronous implementation of filter banks on graphs. In the proposed algorithm nodes follow a randomized collect-compute-broadcast scheme: if a node is in the passive stage it collects the data sent by its incoming neighbors and stores only the most recent data. When a node gets into the active stage at a random time instance, it does the necessary filtering computations locally, and broadcasts a state vector to its outgoing neighbors. When the underlying filters (of the filter bank) are rational functions with the same denominator, the proposed filter bank implementation does not require additional communication between the neighboring nodes. However, computations done by a node increase linearly with the number of filters in the bank. It is also proven that the proposed asynchronous implementation converges to the desired output of the filter bank in the mean-squared sense under mild stability conditions. The convergence is verified also with numerical experiments. 

In recent years the convergence behavior of random node asynchronous graph communications have been studied for the case of undirected graphs. This paper extends these results to the case of graphs having arbitrary directed edges possibly with a nondiagonalizable adjacency matrix. Assuming that the graph operator has eigenvalue 1 and the input signal satisfies a certain condition (which ensures the existence of fixed points), this study presents the necessary and sufficient condition for the mean-squared convergence of the graph signal. The presented condition depends on the graph operator as well as the update probabilities, and the convergence of the randomized asynchronous updates may be achieved even when the underlying operator is not stable in the synchronous setting. As an application, the node-asynchronous updates are combined with polynomial filtering in order to obtain a spectral clustering for directed networks. The convergence is also verified with numerical simulations. 

This study considers a randomized asynchronous form of the discrete time-invariant state-space models, in which only a random subset of the state variables is updated in each iteration. When the system has a single input in the form of a complex exponential, it is shown that the output signal still behaves like an exponential in a statistical sense. The study presents the necessary and sufficient condition that ensures the stability of a randomized asynchronous system, which does not necessarily require the stability of the state transition matrix. 

This paper considers a node-asynchronous implementation of rational (“IIR”) filters on graphs, in which the nodes are assumed to wake up randomly and independently from each other, and communicate only with their immediate neighbors. The underlying graph is allowed to be directed, possibly with a non-diagonalizable adjacency matrix. Since the nodes are allowed to act independently, the proposed implementation is practical for very large or autonomous networks where synchronization is difficult to achieve. Furthermore, the proposed algorithm is 1-hop localized on the graph irrespective of the order of the filter. The method is shown to converge in the mean-squared sense under a boundedness assumption on the filter as well as the graph operator. The result follows from the convergence of a more general randomized asynchronous state recursion, which is also presented in this paper. The algorithm is simulated on a random geometric graph, which numerically verifies the convergence. 

In classical signal processing spectral concentration is an important problem that was first formulated and analyzed by Slepian. The solution to this problem gives the optimal FIR filter that can confine the largest amount of energy in a specific bandwidth for a given filter order. The solution is also known as the prolate sequence. This study investigates the same problem for polynomial graph filters. The problem is formulated in both graph-free and graph-dependent fashions. The graph-free formulation assumes a continuous graph spectrum, in which case it becomes the polynomial concentration problem. This formulation has a universal approach that provides a theoretical reference point. However, in reality graphs have discrete spectrum. The graph-dependent formulation assumes that the eigenvalues of the graph are known and formulates the energy compaction problem accordingly. When the eigenvalues of the graph have a uniform distribution, the graph-dependent formulation is shown to be asymptotically equivalent to the graph-free formulation. However, in reality eigenvalues of a graph tend to have different densities across the spectrum. Thus, the optimal filter depends on the underlying graph operator, and a filter cannot be universally optimal for every graph. 

The notion of graph shift, introduced recently in graph signal processing, extends many classical signal processing techniques to graphs. Its practical importance follows from its localization: a single graph shift requires nodes to communicate only with their neighbors. However, communications should happen simultaneously, which requires a synchronization over the graph. In order to overcome this restriction, recent studies consider a random asynchronous variant of the graph shift, which is also suitable for autonomous networks. A graph signal under this randomized scheme is shown to converge (under mild conditions) to an eigenvector of the eigenvalue 1 of the operator even if the operator has other eigenvalues with magnitudes larger than unity. If the eigenvalue 1 does not exist, the operator can be easily normalized in theory. However, in practice, the normalization requires one to know the (dominant) eigenvalues, which may not be possible to obtain in large autonomous networks. To eliminate this limitation, this study considers the use of a nonlinearity in the updates making the scheme similar in spirit to the Hopfield neural network model. Our simulation results show that a graph signal still approaches the eigenvector of the dominant eigenvalue although the convergence is not exact. Nevertheless, approximation is sufficient to accomplish certain tasks including autonomous clustering. 

This paper considers a random component-wise variant of the unnormalized power method, which is similar to the regular power iteration except that only a random subset of indices is updated in each iteration. For the case of normal matrices, it was previously shown that random component-wise updates converge in the mean-squared sense to an eigenvector of eigenvalue 1 of the underlying matrix even in the case of the matrix having spectral radius larger than unity. In addition to the enlarged convergence regions, this study shows that the eigenvalue gap does not directly aect the convergence rate of the randomized updates unlike the regular power method. In particular, it is shown that the rate of convergence is aected by the phase of the eigenvalues in the case of random component-wise updates, and the randomized updates favor negative eigenvalues over positive ones. As an application, this study considers a reformulation of the component-wise updates revealing a randomized algorithm that is proven to converge to the dominant left and right singular vectors of a normalized data matrix. The algorithm is also extended to handle large-scale distributed data when computing an arbitrary rank approximation of an arbitrary data matrix. Numerical simulations verify the convergence of the proposed algorithms under dierent parameter settings.